package Algorithm.Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author cj
 * @Date 2022/9/14 21:43
 */
public class getPosArray {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    public int[] getPosArray1(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        int len = pre.length;
        int[] pos = new int[len];
        // 记录中序数组值与下标关系
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(in[i], i);
        }
        setPos(pre, 0, len - 1, in, 0, len - 1, pos, len - 1, map);
        return pos;
    }

    // 返回值是后序数组需要填充的下标
    private int setPos(int[] pre, int pi, int pj, int[] in,
                        int ini, int inj, int[] pos, int posIndex, Map<Integer, Integer> map) {
        if (pi > pj) {
            return posIndex;
        }
        // 设置后序根节点
        pos[posIndex--] = pre[pi];
        // 找到根节点对应中序数组的下标
        int i = map.get(pi);
        // 递归右子树
        posIndex = setPos(pre, pj - inj + i + 1, pj, in, i + 1, inj, pos, posIndex, map);
        // 递归左子树
        return setPos(pre, pi + 1, pi + i - ini, in, ini, i - 1, pos, posIndex, map);
    }
}
